package first

/*
	一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

	示例 1：

	输入：nums = [4,1,4,6]
	输出：[1,6] 或 [6,1]
	示例 2：

	输入：nums = [1,2,10,4,1,4,3,3]
	输出：[2,10] 或 [10,2]

	限制：

	2 <= nums.length <= 10000

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
/*
	答案很简单：全员进行异或操作即可。考虑异或操作的性质：对于两个操作数的每一位，相同结果为 00，不同结果为 11。那么在计算过程中，
	成对出现的数字的所有位会两两抵消为 00，最终得到的结果就是那个出现了一次的数字。

那么这一方法如何扩展到找出两个出现一次的数字呢？

如果我们可以把所有数字分成两组，使得：

两个只出现一次的数字在不同的组中；

相同的数字会被分到相同的组中。

那么对两个组分别进行异或操作，即可得到答案的两个数字。这是解决这个问题的关键。

那么如何实现这样的分组呢？

记这两个只出现了一次的数字为 aa 和 bb，那么所有数字异或的结果就等于 aa 和 bb 异或的结果，我们记为 xx。如果我们把 xx 写成二进制的形式 x_k x_{k - 1} \cdots x_2 x_1 x_0x
k
​
 x
k−1
​
 ⋯x
2
​
 x
1
​
 x
0
​
 ，其中 x_i \in \{ 0, 1 \}x
i
​
 ∈{0,1}，我们考虑一下 x_i = 0x
i
​
 =0 和 x_i = 1x
i
​
 =1 的含义是什么？它意味着如果我们把 aa 和 bb 写成二进制的形式，a_ia
i
​
  和 b_ib
i
​
  的关系——x_i = 1x
i
​
 =1 表示 a_ia
i
​
  和 b_ib
i
​
  不等，x_i = 0x
i
​
 =0 表示 a_ia
i
​
  和 b_ib
i
​
  相等。假如我们任选一个不为 00 的 x_ix
i
​
 ，按照第 ii 位给原来的序列分组，如果该位为 00 就分到第一组，否则就分到第二组，这样就能满足以上两个条件，为什么呢？

首先，两个相同的数字的对应位都是相同的，所以一个被分到了某一组，另一个必然被分到这一组，所以满足了条件 2。

这个方法在 x_i = 1x
i
​
 =1 的时候 aa 和 bb 不被分在同一组，因为 x_i = 1x
i
​
 =1 表示 a_ia
i
​
  和 b_ib
i
​
  不等，根据这个方法的定义「如果该位为 00 就分到第一组，否则就分到第二组」可以知道它们被分进了两组，所以满足了条件 1。

在实际操作的过程中，我们拿到序列的异或和 xx 之后，对于这个「位」是可以任取的，只要它满足 x_i = 1x
i
​
 =1。但是为了方便，这里的代码选取的是「不为 00 的最低位」，当然你也可以选择其他不为 00 的位置。

至此，答案已经呼之欲出了。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/solution/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/
func singleNumbers(nums []int) []int {
	ret := 0
	for _, num := range nums {
		ret ^= num
	}
	mask := 1
	for mask&ret == 0 {
		mask <<= 1 // 找到异或结果第一位不为0的二进制位
	}
	a, b := 0, 0
	// 分组
	/*
		因为确定只存在两个只出现一次的数字、所以可以分成两组、分组方式如下：
		1. 对于出现两次的数字、确保这两个数字分到同一组
		2. 对于两个只出现一次的数字、确保分到不同的组
		找到数组异或结果中任意一个为1的二进制位mask、以此进行分组、所有元素该位为0的分到一组、该位为1的分到另一组、即将数组中所有元素与mask进行按位与
		按位与结果为0的位一组、不为0的为另一组、推论如下：
		1. 相同的数字二进制位是相同的、要么为0，要么为1、所以可以确保通过该方式将相同的数字分配到同一组
		2. 两个只出现一次的数字、其异或结果1表示两个数字在该位的值不相同、一个为0、一个为1、则与mask的按位与结果应该是一个为0、一个为1、所以可以确保这两个数字分在不同组

	*/
	for _, num := range nums {
		if mask&num == 0 {
			a ^= num
		} else {
			b ^= num
		}
	}
	return []int{a,b}
}
